package Algorithm.Greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code05_LineMaxCovers {

    public static class Line{
        public int start;
        public int end;

        public Line(int s, int e){
            start = s;
            end = e;
        }
    }

    public static class StartComparator implements Comparator<Line> {

        @Override
        public int compare(Line o1, Line o2){
            return o1.start - o2.start;
        }
    }

    public static class EndComparator implements Comparator<Line> {

        @Override
        public int compare(Line o1, Line o2){
            return o1.end - o2.end;
        }
    }

    // 求最大重合部分上盖了多少线段
    // 要求重合部分长度>0
    public static int maxCovers(int[] start, int[] end){
        if (start ==null || end == null || start.length != end.length){
            return 0;
        }
        PriorityQueue<Line> startMinHeap = new PriorityQueue<>(new StartComparator());
        for (int i = 0; i < start.length; i++){
            if (start[i] < end[i]){
                startMinHeap.add(new Line(start[i], end[i]));
            }
        }
        PriorityQueue<Line> endMinHeap = new PriorityQueue<>(new EndComparator());
        int max = 0;
        while (!startMinHeap.isEmpty()){
            Line cur = startMinHeap.poll();
            while (!endMinHeap.isEmpty() && endMinHeap.peek().end <= cur.start){
                endMinHeap.poll();
            }
            endMinHeap.add(cur);
            max = Math.max(max, endMinHeap.size());
        }
        return max;
    }

    public static void main(String[] args) {
        int[] start = {1, 1,1,2,5};
        int[] end = {7,4,9,13,10};
        System.out.println(maxCovers(start, end));
    }
}
